package array;

public class BinarySearchMatrix
{
  
  public class Result{
    int row;
    int col;
  }
  
  boolean binPart(int mat[][], int target, int l, int u, int r, int d, Result result) {
    if (l > r || u > d) return false;
    if (target < mat[u][l] || target > mat[d][r]) return false;
    int mid = l + (r-l)/2;
    int row = u;
    while (row <= d && mat[row][mid] <= target) {
      if (mat[row][mid] == target) {
        result.row = row;
        result.col = mid;
        return true;
      }
      row++;
    }
    return binPart(mat, target, mid+1, u, r, row-1, result) ||
           binPart(mat, target, l, row, mid-1, d, result);
  }
  
  public Result bs(int mat[][], int target){
    Result r = new Result();
    binPart(mat, target, 0,0,mat.length,mat[0].length, r);
    return r;
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

  }

}
